home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 November: Tool Chest / Dev.CD Nov 94.toast / Sample Code / Snippets / Development Tools & Languages / DTSCPlusLibrary / Sources / CollectionClasses.h < prev    next >
Encoding:
Text File  |  1993-01-14  |  6.2 KB  |  208 lines  |  [TEXT/MPS ]
  1. /* _________________________________________________________________________________________________________ //
  2.   Copyright © 1992-93 Apple Computer, Inc. All rights reserved.
  3.   Macintosh Developer Technical Support.C++ Macintosh Toolbox Framework.
  4.   Programmer: Kent Sandvik
  5.   Date: 11/7/92
  6.   Revision comments are at the end of this file.
  7.   ---
  8.   The following collection classes are implemented: TLinkedList, TStack, (TQueue, TDeQueue),
  9.   THashTable.
  10.   CollectionClasses.h contains the collection class definitions. 
  11.   _________________________________________________________________________________________________________ */
  12.  
  13. // Declare label for this header file
  14. #ifndef _COLLECTION__
  15. #define _COLLECTION__
  16.  
  17. #ifndef _DTSCPLUSLIBRARY_
  18. #include "DTSCPlusLibrary.h"
  19. #endif
  20.  
  21. //    GLOBAL CONSTRUCTS
  22. typedef unsigned long TItemtype;
  23. //typedef void* TItemtype;
  24.  
  25. // Note that we need to define this for the collecion items --
  26. // when we have tempates this will be moot!
  27. // Note that void* is the most practical one concerning storing
  28. // data structure pointers in lists, queues and stacks (typedef void * TItemtype)
  29.  
  30. const kCollectionSize = 200;                    // tune this concerning performance
  31.  
  32.  
  33. // _________________________________________________________________________________________________________ //
  34. //    TLinkedList Class Interface.
  35.  
  36. class TLinkedList
  37. {
  38. public:
  39.     //    CONSTRUCTORS AND DESTRUCTORS
  40.     TLinkedList(short max = kCollectionSize);
  41.     virtual~ TLinkedList();
  42.  
  43.     // MAIN INTERFACES
  44.     virtual Boolean Append(const TItemtype item);// add an entry to the linked list
  45.     virtual Boolean Remove(const TItemtype item);// remove defined item from the linked list
  46.  
  47.     virtual Boolean IsEmpty();                    // check if the collection has zero entries
  48.     virtual Boolean Find(const TItemtype item);    // find out if a special item type is in the list
  49.  
  50.     virtual Size GetSize() const;                // get amount of entries in collection
  51.  
  52.     // ITERATORS
  53.     virtual TItemtype First();                    // return first entry
  54.     virtual TItemtype Next();                    // return next entry
  55.     virtual TItemtype Last();                    // return last entry
  56.     virtual void Reset();                        // move iterator to first entry        
  57.  
  58.     //    FIELDS
  59. protected:
  60.     short fMaxCollectionSize;                    // max entries in the collection
  61.     short fCollectionSize;                        // current amount of entries in the collection
  62.     struct fNODE                                // our pointer list structure
  63.     {
  64.         TItemtype fKey;
  65.         struct fNODE *fNext;
  66.         struct fNODE *fPrevious;                // for future use
  67.     };
  68.  
  69.  
  70.     struct fNODE *fHead, * fTail, * fLastEntry, * fCurrentNode;
  71.     // linked list pointers: forward, backward, last entry, current
  72. };
  73.  
  74.  
  75. // _________________________________________________________________________________________________________ //
  76. //    TStack Class Interface.
  77.  
  78. class TStack : public TLinkedList
  79. {
  80. public:
  81.     // CONSTRUCTORS AND DESTRUCTORS
  82.     TStack(short max = kCollectionSize);
  83.     virtual~ TStack();
  84.  
  85.     // MAIN INTERFACES
  86.     virtual Boolean Push(const TItemtype item);    // push on the 'stack'
  87.     virtual Boolean Append(const TItemtype item);// will just call push anyway
  88.     virtual TItemtype Pop();                    // pop from the 'stack'
  89.     virtual Boolean Remove(const TItemtype item);// not supported, will return false
  90. };
  91.  
  92.  
  93. class TQueue : public TLinkedList
  94. {
  95. public:
  96.     // CONSTRUCTORS AND DESTRUCTORS
  97.     TQueue(short max = kCollectionSize);
  98.     ~TQueue();
  99.  
  100.     // MAIN INTERFACE
  101.     virtual Boolean Put(const TItemtype item);    // put at the beginning of the queue
  102.     virtual Boolean Append(const TItemtype item);// will just call put anyway
  103.     virtual TItemtype Get();                    // get from the end of the queue
  104.     virtual TItemtype Last();                    // get the one at the end
  105.     virtual Boolean Remove(const TItemtype item);// not supported, will return false
  106. };
  107.  
  108.  
  109. class TDeque : public TQueue
  110. {
  111. public:
  112.     // CONSTRUCTORS AND DESTRUCTORS
  113.     TDeque(short max = kCollectionSize);
  114.     virtual~ TDeque();
  115.  
  116.     // MAIN INTERFACE
  117.     virtual Boolean Push(const TItemtype item);    // will call Put anyway
  118.     virtual Boolean PutAtEnd(const TItemtype item);// add entry to the end of the dequeue
  119.  
  120.     virtual TItemtype Pop();                    // remove from beginning of deque
  121. };
  122.  
  123.  
  124.  
  125. // _________________________________________________________________________________________________________ //
  126. //    THashEntry Class Interface.
  127.  
  128. // globals, constants, enums and typedefs
  129. const unsigned long kResourceIDMask = 0xFFFFF;
  130. const NBUCKETS = 256;                            // amount of buckets in our hash entry array    
  131.  
  132.  
  133. typedef unsigned long THashKey;                    // define our hash key type
  134. typedef void(* MapFun)(void*);                    // our MapCar function definition
  135.  
  136.  
  137. // Our Hash Bucket entry data structure
  138. class THashEntry                                // embedded bucket for hash ptrs and values
  139. {
  140. public:
  141.     THashKey fKey;                                // hash key
  142.     TItemtype fValue;                            // value in bucket
  143.     THashEntry* fNext, * fPrevious;                // pointers to other buckets
  144.  
  145.     THashEntry(THashKey key)                    // constructor for this mini class
  146.     {
  147.         fKey = key;
  148.         fNext = NULL;
  149.         fPrevious = NULL;
  150.     }
  151.  
  152.  
  153.     ~THashEntry()
  154.     {
  155.         if (fNext)
  156.             fNext->fPrevious = fPrevious;
  157.         if (fPrevious)
  158.             fPrevious->fNext = fNext;
  159.     }
  160. };
  161.  
  162.  
  163. typedef THashEntry* THashEntryPtr;                // we are using a ptr quite a lot in the THashTable implementation
  164.  
  165.  
  166. // The THashTable class definition
  167. class THashTable
  168. {
  169. public:
  170.     // CONSTRUCTORS AND DESTRUCTORS
  171.     THashTable();
  172.     virtual~ THashTable();
  173.  
  174.     // MAIN INTERFACE
  175.     virtual Boolean Add(THashKey key,
  176.                         TItemtype value);        // add to hash table
  177.     virtual Boolean Remove(THashKey key);        // remove from hash table
  178.     virtual TItemtype Find(THashKey key);        // find entry in hash table
  179.     virtual void MapCar(MapFun function);        // iterate with a function over hash table entries
  180.  
  181.  
  182.     // PRIVATE INTERNAL FUNCTIONS
  183. protected:
  184.     THashEntryPtr AddElement(THashKey key);        // add an element to the hash table
  185.     virtual THashKey Hash(THashKey key);        // create the hash value
  186.     virtual THashEntryPtr FindInBucket(THashEntryPtr p,
  187.                                        // find inside the bucket the element
  188.                                        THashKey key);
  189.  
  190.     // FIELDS
  191. protected:
  192.     THashEntryPtr fBucket[NBUCKETS];            // our internal class bucket with entries
  193. };
  194.  
  195.  
  196. #endif
  197.  
  198. // _________________________________________________________________________________________________________ //
  199.  
  200.  
  201. /*    Change History (most recent last):
  202.   No        Init.    Date        Comment
  203.   1            khs        11/7/92        New file
  204.   2            khs        11/28/92    Added TLinkedList
  205.   3            khs        11/29/92    Added TQueue and TDeque
  206.   4            khs        1/14/93        Cleanup
  207. */
  208.